package com.company;

import java.io.IOException;
import java.util.*;

/**
 * Created by v on 17-5-9.
 */
public class Main {
    public static void main(String[] args) throws IOException{
        HashMap<String,LinkedList<String>> map=Input.map();
        Iterator<Map.Entry<String,LinkedList<String>>> iterator=map.entrySet().iterator();

        //用来储存图下标的哈希表
        HashMap<String,Integer> index=new HashMap<>();
        int current=0;
        //建立一个大小为1万的不相交集
        DisjSets sets=new DisjSets(10000);

        //用不相交集构建图
        while (iterator.hasNext()){
            Map.Entry<String,LinkedList<String>> entry=iterator.next();
            //出发点的名字
            String name=entry.getKey();
            //邻接的其他点
            LinkedList<String> list=entry.getValue();

            //如果索引里面没有这个点，则把这个点标记到哈希表里面
            if(!index.containsKey(name)){
                index.put(name,current++);
            }

            int point1=index.get(name);

            for(String str:list){
                if(!index.containsKey(str)){
                    index.put(str,current++);
                }
                int point2=index.get(str);

                //根据索引在不相交集中查找他们两个的连通分支
                int root1=sets.find(point1);
                int root2=sets.find(point2);

                if(root1!=root2){
                    sets.union(root1,root2);
                }
            }
        }

        Scanner input=new Scanner(System.in);
        while (true){
            System.out.println("请依次输入两个点");
            String str1=input.next();
            String str2=input.next();

            //判断是否会出现错误输入
            if((!index.containsKey(str1))||(!index.containsKey(str2))){
                System.out.println("您输入的点有误");
                continue;
            }
            //通过哈希表找到点的索引值
            int index1=index.get(str1);
            int index2=index.get(str2);

            //计时开始
            long time=System.nanoTime();

            //通过索引在不相交集中寻找是否连通
            if(sets.find(index1)==sets.find(index2)){
                System.out.println("两个点是连通的");
            }else{
                System.out.println("两个点不连通");
            }
            System.out.println(System.nanoTime()-time+"纳秒");
        }
    }
}
